package main

import (
	"fmt"
)

// 定义链表节点
type ListNode struct {
	Val  int
	Next *ListNode
}

// 创建新节点
func newNode(val int) *ListNode {
	return &ListNode{Val: val, Next: nil}
}

// 合并两个有序链表
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
	// 创建一个哑节点，简化代码逻辑
	dummy := newNode(0)
	curr := dummy

	// 遍历两个链表，将值较小的节点接在结果链表后面
	for l1 != nil && l2 != nil {
		if l1.Val < l2.Val {
			curr.Next = l1
			l1 = l1.Next
		} else {
			curr.Next = l2
			l2 = l2.Next
		}
		curr = curr.Next
	}

	// 将剩余的节点接在结果链表后面
	if l1 != nil {
		curr.Next = l1
	} else {
		curr.Next = l2
	}

	// 返回结果链表的头节点
	return dummy.Next
}

// 归并排序
func sortList(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}

	// 使用快慢指针找到链表中点
	slow, fast := head, head
	var prev *ListNode
	for fast != nil && fast.Next != nil {
		prev = slow
		slow = slow.Next
		fast = fast.Next.Next
	}

	// 断开链表
	prev.Next = nil

	// 递归排序左右两个链表
	left := sortList(head)
	right := sortList(slow)

	// 合并已排序的左右链表
	return mergeTwoLists(left, right)
}

// 打印链表
func printList(head *ListNode) {
	for head != nil {
		fmt.Printf("%d", head.Val)
		if head.Next != nil {
			fmt.Printf(" -> ")
		}
		head = head.Next
	}
	fmt.Println("")
}

func main() {
	// 创建一个链表
	head := newNode(4)
	head.Next = newNode(2)
	head.Next.Next = newNode(1)
	head.Next.Next.Next = newNode(3)

	// 打印原始链表
	fmt.Println("原始链表:")
	printList(head)

	// 排序链表
	head = sortList(head)

	// 打印排序后的链表
	fmt.Println("排序后的链表:")
	printList(head)
}
